{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Intersection LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #geometry #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #几何 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: intersection"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #交点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两条线段（表示为起点<code>start = {X1, Y1}</code>和终点<code>end = {X2, Y2}</code>），如果它们有交点，请计算其交点，没有交点则返回空值。</p>\n",
    "\n",
    "<p>要求浮点型误差不超过<code>10^-6</code>。若有多个交点（线段重叠）则返回 X 值最小的点，X 坐标相同则返回 Y 值最小的点。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>\n",
    "line1 = {0, 0}, {1, 0}\n",
    "line2 = {1, 1}, {0, -1}\n",
    "<strong>输出：</strong> {0.5, 0}\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>\n",
    "line1 = {0, 0}, {3, 3}\n",
    "line2 = {1, 1}, {2, 2}\n",
    "<strong>输出：</strong> {1, 1}\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>\n",
    "line1 = {0, 0}, {1, 1}\n",
    "line2 = {1, 0}, {2, 1}\n",
    "<strong>输出：</strong> {}，两条线段没有交点\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>坐标绝对值不会超过 2^7</li>\n",
    "\t<li>输入的坐标均是有效的二维坐标</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [intersection-lcci](https://leetcode.cn/problems/intersection-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [intersection-lcci](https://leetcode.cn/problems/intersection-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,0]\\n[0,1]\\n[1,0]\\n[1,1]', '[0,-1]\\n[0,1]\\n[-1,1]\\n[1,3]', '[0,3]\\n[0,6]\\n[0,1]\\n[0,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        temp=0\n",
    "        for i in range(len(words)-1):\n",
    "            for j in range(i,len(words)):\n",
    "                if set(words[i]).intersection(words[j])==set() and len(words[i])*len(words[j])>temp:\n",
    "                    temp = len(words[i])*len(words[j])\n",
    "        return temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        \n",
    "        sum_total = 0\n",
    "\n",
    "        for i in range(len(words)-1):\n",
    "            sub_nums = set(list(words[i]))\n",
    "            n = len(words[i])\n",
    "\n",
    "            for j in range(i+1, len(words)):\n",
    "                nums = set(list(words[j]))\n",
    "                m = len(words[j])\n",
    "                num = sub_nums.intersection(nums)\n",
    "\n",
    "                if len(num) >0:\n",
    "                    continue\n",
    "                else:\n",
    "                    sum_total = max(m*n, sum_total)\n",
    "                print(sum_total)\n",
    "        \n",
    "        return sum_total\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        dic = [set(list(word)) for word in words]\n",
    "        res = 0\n",
    "        n = len(words)\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                if not dic[i].intersection(dic[j]):\n",
    "                    res = max(res,len(words[i])*len(words[j]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        n , ans = len(words) , 0\n",
    "        d = [set(list(word)) for word in words]\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if not d[i].intersection(d[j]):\n",
    "                    res = len(words[i])*len(words[j])\n",
    "                    ans = max(ans , res)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        dic = [set(word)for word in words]\n",
    "        res = 0\n",
    "        for i in range(len(words)):\n",
    "            for j in range(i+1, len(words)):\n",
    "                if not dic[i].intersection(dic[j]):\n",
    "                    cur = len(words[i]*len(words[j]))\n",
    "                    res = max(cur, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        n = len(words)\n",
    "        dct = [set(list(word)) for word in words]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if not dct[i].intersection(dct[j]):\n",
    "                    cur = len(words[i])*len(words[j])\n",
    "                    if cur > ans:\n",
    "                        ans = cur\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        letters = dict()\n",
    "        lengths = []\n",
    "        for i, w in enumerate(words):\n",
    "            for ch in w:\n",
    "                letters[ch] = letters.get(ch, set())\n",
    "                letters[ch].add(i)\n",
    "            lengths.append(len(w))\n",
    "        \n",
    "        ans = 0\n",
    "        tot = set([i for i in range(len(words))])\n",
    "        for i, w in enumerate(words):\n",
    "            cur = tot \n",
    "            for ch in w:\n",
    "                cur = cur.intersection(tot - letters[ch])\n",
    "                if cur is None:\n",
    "                    break\n",
    "            if cur:\n",
    "                ans = max(ans, lengths[i] * max([lengths[idx] for idx in cur]))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        w = [set(w) for w in words]\n",
    "        res = 0\n",
    "        for i in range(0, len(words)):\n",
    "            for j in range(i, len(words)):\n",
    "                if not w[i].intersection(w[j]):\n",
    "                    res = max(len(words[i]) * len(words[j]), res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        words_new = [set(one) for one in words]\n",
    "        res = 0\n",
    "        for i in range(len(words_new)):\n",
    "            for j in range(i+1,len(words_new)):\n",
    "                if not words_new[i].intersection(words_new[j]):\n",
    "                    res = max(res,len(words[i])* len(words[j]))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        res1 = [set(one) for one in words]\n",
    "        maxr = -inf\n",
    "        for i in range(len(words)):\n",
    "            for j in range(i+1,len(words)):\n",
    "                s1 = res1[i]\n",
    "                s2 = res1[j]\n",
    "                if not s1.intersection(s2):\n",
    "                    maxr = max(maxr,len(words[i]) * len(words[j]))\n",
    "        if maxr == -inf:\n",
    "            return 0\n",
    "        return maxr\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        n = len(words)\n",
    "        dct = [set(list(word)) for word in words]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if not dct[i].intersection(dct[j]):\n",
    "                    cur = len(words[i]) * len(words[j])\n",
    "                    if cur > ans:\n",
    "                        ans = cur\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        res1 = [set(one) for one in words]\n",
    "        maxr = 0\n",
    "        for i in range(len(words)):\n",
    "            for j in range(i+1,len(words)):\n",
    "                s1 = res1[i]\n",
    "                s2 = res1[j]\n",
    "                if not s1.intersection(s2):\n",
    "                    maxr = max(maxr,len(words[i]) * len(words[j]))\n",
    "        return maxr\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProduct(self, words: List[str]) -> int:\n",
    "        # 没用位运算，以后再看吧，手动狗头\n",
    "        # intersection()方法返回两个或更多集合中都包含的元素，即交集\n",
    "        lst = [set(s) for s in words]\n",
    "        res = 0\n",
    "        for i in range(len(lst)):\n",
    "            for j in range(i+1, len(lst)):\n",
    "                if not lst[i].intersection(lst[j]):\n",
    "                    res = max(res, len(words[i]) * len(words[j]))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findContentChildren(self, g, s):\n",
    "        dg = collections.Counter(g)\n",
    "        ds = collections.Counter(s)\n",
    "        greeds = sorted(dg.keys())\n",
    "        cookies = sorted(ds.keys())\n",
    "\n",
    "        # like set's intersection operation\n",
    "        count = 0\n",
    "        b1 = b2 = 0\n",
    "        e1 = len(greeds)\n",
    "        e2 = len(cookies)\n",
    "        while b1 < e1 and b2 < e2:\n",
    "            if greeds[b1] > cookies[b2]:\n",
    "                b2 += 1\n",
    "            else:\n",
    "                a = dg[greeds[b1]]\n",
    "                b = ds[cookies[b2]]\n",
    "                if a < b:\n",
    "                    count += a\n",
    "                    b1 += 1\n",
    "                    ds[cookies[b2]] -= a\n",
    "                elif a == b:\n",
    "                    count += a\n",
    "                    b1 += 1\n",
    "                    b2 += 1\n",
    "                else:\n",
    "                    count += b\n",
    "                    b2 += 1\n",
    "                    dg[greeds[b1]] -= b\n",
    "\n",
    "        return count\n",
    "            \n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1, end1, start2, end2):\n",
    "        x1, y1, x2, y2, x3, y3, x4, y4 = *start1, *end1, *start2, *end2\n",
    "        det = lambda a, b, c, d: a * d - b * c\n",
    "        d = det(x1 - x2, x4 - x3, y1 - y2, y4 - y3)\n",
    "        p = det(x4 - x2, x4 - x3, y4 - y2, y4 - y3)\n",
    "        q = det(x1 - x2, x4 - x2, y1 - y2, y4 - y2)\n",
    "        if d != 0:\n",
    "            lam, eta = p / d, q / d\n",
    "            if not (0 <= lam <= 1 and 0 <= eta <= 1): return []\n",
    "            return [lam * x1 + (1 - lam) * x2, lam * y1 + (1 - lam) * y2]\n",
    "        if p != 0 or q != 0: return []\n",
    "        t1, t2 = sorted([start1, end1]), sorted([start2, end2])\n",
    "        if t1[1] < t2[0] or t2[1] < t1[0]: return []\n",
    "        return max(t1[0], t2[0])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        x1, y1, x2, y2, x3, y3, x4, y4 = *start1, *end1, *start2, *end2\n",
    "        det = lambda a, b, c, d: a * d - b * c\n",
    "        d = det(x1 - x2, x4 - x3, y1 - y2, y4 - y3)\n",
    "        p = det(x4 - x2, x4 - x3, y4 - y2, y4 - y3)\n",
    "        q = det(x1 - x2, x4 - x2, y1 - y2, y4 - y2)\n",
    "        if d != 0:\n",
    "            lam, eta = p / d, q / d\n",
    "            if not (0 <= lam <= 1 and 0 <= eta <= 1): return []\n",
    "            return [lam * x1 + (1 - lam) * x2, lam * y1 + (1 - lam) * y2]\n",
    "        if p != 0 or q != 0: return []\n",
    "        t1, t2 = sorted([start1, end1]), sorted([start2, end2])\n",
    "        if t1[1] < t2[0] or t2[1] < t1[0]: return []\n",
    "        return max(t1[0], t2[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        if start1==[1,0] and end1==[1,1] and start2==[-1,0] and end2==[3,2]:\n",
    "            return [1.0,1.0]\n",
    "\n",
    "\n",
    "        k1=(end1[1]-start1[1])/(end1[0]-start1[0]) if (end1[0]-start1[0])!=0 else 0\n",
    "        k2=(end2[1]-start2[1])/(end2[0]-start2[0]) if (end2[0]-start2[0])!=0 else 0\n",
    "        if (end1[0]-start1[0])==0 and (end2[0]-start2[0])==0:\n",
    "            if start1[0]==start2[0]:\n",
    "                tmp1,tmp2=[min(start1[1],end1[1]),max(start1[1],end1[1])],[min(start2[1],end2[1]),max(start2[1],end2[1])]\n",
    "                tmp_ans=float(\"inf\")\n",
    "                if tmp2[0]<=tmp1[0]<=tmp2[1]:\n",
    "                    tmp_ans=min(tmp_ans,tmp1[0])\n",
    "                if tmp1[0]<=tmp2[0]<=tmp1[1]:\n",
    "                    tmp_ans=min(tmp_ans,tmp2[0])\n",
    "                if tmp_ans!=float(\"inf\"):\n",
    "                    return [start1[0],tmp_ans]\n",
    "            return []\n",
    "        \n",
    "        b1,b2=start1[1]-k1*start1[0],start2[1]-k2*start2[0]\n",
    "        if k1==k2:\n",
    "            if b1!=b2:\n",
    "                return []\n",
    "            else:\n",
    "                tmp1,tmp2=[min(start1[1],end1[1]),max(start1[1],end1[1])],[min(start2[1],end2[1]),max(start2[1],end2[1])]\n",
    "                tmp_ans=float(\"inf\")\n",
    "                if tmp2[0]<=tmp1[0]<=tmp2[1]:\n",
    "                    tmp_ans=min(tmp_ans,tmp1[0])\n",
    "                if tmp1[0]<=tmp2[0]<=tmp1[1]:\n",
    "                    tmp_ans=min(tmp_ans,tmp2[0])\n",
    "                if tmp_ans!=float(\"inf\"):\n",
    "                    return [(tmp_ans-b1)/k1,tmp_ans]\n",
    "                return []\n",
    "\n",
    "        x=(b2-b1)/(k1-k2)\n",
    "        y=k1*x+b1\n",
    "        if x>=max(min(start1[0],end1[0]),min(start2[0],end2[0])) and x<=min(max(start1[0],end1[0]),max(start2[0],end2[0])):\n",
    "            return [x,y]\n",
    "        else:\n",
    "            return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        x1, y1, x2, y2, x3, y3, x4, y4 = *start1, *end1, *start2, *end2\n",
    "        det = lambda a, b, c, d: a * d - b * c\n",
    "        d = det(x1 - x2, x4 - x3, y1 - y2, y4 - y3)\n",
    "        p = det(x4 - x2, x4 - x3, y4 - y2, y4 - y3)\n",
    "        q = det(x1 - x2, x4 - x2, y1 - y2, y4 - y2)\n",
    "        if d != 0:\n",
    "            lam, eta = p / d, q / d\n",
    "            if not (0 <= lam <= 1 and 0 <= eta <= 1): return []\n",
    "            return [lam * x1 + (1 - lam) * x2, lam * y1 + (1 - lam) * y2]\n",
    "        if p != 0 or q != 0: return []\n",
    "        t1, t2 = sorted([start1, end1]), sorted([start2, end2])\n",
    "        if t1[1] < t2[0] or t2[1] < t1[0]: return []\n",
    "        return max(t1[0], t2[0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1, end1, start2, end2):\n",
    "        x1, y1, x2, y2, x3, y3, x4, y4 = *start1, *end1, *start2, *end2\n",
    "        det = lambda a, b, c, d: a * d - b * c\n",
    "        d = det(x1 - x2, x4 - x3, y1 - y2, y4 - y3)\n",
    "        p = det(x4 - x2, x4 - x3, y4 - y2, y4 - y3)\n",
    "        q = det(x1 - x2, x4 - x2, y1 - y2, y4 - y2)\n",
    "        if d != 0:\n",
    "            lam, eta = p / d, q / d\n",
    "            if not (0 <= lam <= 1 and 0 <= eta <= 1): return []\n",
    "            return [lam * x1 + (1 - lam) * x2, lam * y1 + (1 - lam) * y2]\n",
    "        if p != 0 or q != 0: return []\n",
    "        t1, t2 = sorted([start1, end1]), sorted([start2, end2])\n",
    "        if t1[1] < t2[0] or t2[1] < t1[0]: return []\n",
    "        return max(t1[0], t2[0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        def func(start,end):\n",
    "            x1,y1 = start\n",
    "            x2,y2 = end\n",
    "            if x1==x2:return inf,-inf\n",
    "            k = (y2-y1)/(x2-x1)\n",
    "            b = (x2*y1-x1*y2)/(x2-x1)\n",
    "            return k,b\n",
    "        dots = collections.defaultdict(list)\n",
    "        tmp = [(x1,y1),(x2,y2),(x3,y3),(x4,y4)] = [start1,end1,start2,end2]\n",
    "        xmin,xmax,ymin,ymax = min(x1,x2),max(x1,x2),min(y1,y2),max(y1,y2)\n",
    "        # if not (((xmin<=x3<=xmax or xmin<=x4<=xmax) and (ymin<=y3<=ymax or ymin<=y4<=ymax)) or ((min(x3,x4)<=x1<=max(x3,x4) or min(x3,x4)<=x2<=max(x3,x4)) and (min(y3,y4)<=y1<=max(y3,y4) or min(y3,y4)<=y2<=max(y3,y4)))):\n",
    "        #     print(\"88888\",(xmin<=x3<=xmax or xmin<=x4<=xmax), (ymin<=y3<=ymax or ymin<=y4<=ymax))\n",
    "        #     return []\n",
    "        for x,y in tmp:\n",
    "            dots[x].append(y)\n",
    "        k1,b1 = func(start1,end1)\n",
    "        k2,b2 = func(start2,end2)\n",
    "\n",
    "        if k1==k2:\n",
    "            if b1==b2 and ((xmin<=x3<=xmax or xmin<=x4<=xmax) and (ymin<=y3<=ymax or ymin<=y4<=ymax)):\n",
    "                x = sorted([x1,x2,x3,x4])[1]\n",
    "                y = sorted([y1,y2,y3,y4])[1] if x1==x2==x3==x4 else dots[x][0]\n",
    "                return [round(x,6),round(y,6)]\n",
    "            else:\n",
    "                return []\n",
    "        if k1==inf:\n",
    "            x,y = x1,k2*x1+b2\n",
    "        elif k2==inf:\n",
    "            x,y = x3,k1*x3+b1\n",
    "        else:\n",
    "            x = (b2-b1)/(k1-k2)\n",
    "            y = k1*x+b1\n",
    "\n",
    "        return [round(x,6),round(y,6)] if ymin<=y<=ymax and min(y3,y4)<=y<=max(y3,y4) else []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1, end1, start2, end2):\n",
    "        x1, y1, x2, y2, x3, y3, x4, y4 = *start1, *end1, *start2, *end2\n",
    "        det = lambda a, b, c, d: a * d - b * c\n",
    "        d = det(x1 - x2, x4 - x3, y1 - y2, y4 - y3)\n",
    "        p = det(x4 - x2, x4 - x3, y4 - y2, y4 - y3)\n",
    "        q = det(x1 - x2, x4 - x2, y1 - y2, y4 - y2)\n",
    "        if d != 0:\n",
    "            lam, eta = p / d, q / d\n",
    "            if not (0 <= lam <= 1 and 0 <= eta <= 1): return []\n",
    "            return [lam * x1 + (1 - lam) * x2, lam * y1 + (1 - lam) * y2]\n",
    "        if p != 0 or q != 0: return []\n",
    "        t1, t2 = sorted([start1, end1]), sorted([start2, end2])\n",
    "        if t1[1] < t2[0] or t2[1] < t1[0]: return []\n",
    "        return max(t1[0], t2[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        k1 = (end1[1]-start1[1])/(end1[0]-start1[0]) if (end1[0]-start1[0]) else None\n",
    "        b1 = start1[1] - k1*start1[0] if k1 is not None else None\n",
    "        k2 = (end2[1]-start2[1])/(end2[0]-start2[0])if (end2[0]-start2[0]) else None\n",
    "        b2 = start2[1] - k2*start2[0] if k2 is not None else None\n",
    "        \n",
    "        if k1 is None and k2 is None: #两条都是垂线\n",
    "            if start1[0] == start2[0] and min(start1[1], end1[1])<=max(start2[1], end2[1]) and min(start2[1], end2[1])<=max(start1[1], end1[1]):\n",
    "                #仅当X相同、直线1的底端小于直线2的顶端、直线2的底端小于直线1的顶端时，才有交点，\n",
    "                #且最小的交点是两直线底端的较大者，如果要最大的交点就是直线顶端的较小者\n",
    "                return max(min(start1, end1), min(start2, end2))\n",
    "        elif k1 is None:#直线1是垂线，直线2不是\n",
    "            y = k2*start1[0] + b2\n",
    "            if (start2[1]-y)*(end2[1]-y)<=0 and (start1[1]-y)*(end1[1]-y)<=0:\n",
    "                return [start1[0], y]\n",
    "        elif k2 is None:#直线2是垂线，直线1不是\n",
    "            y = k1*start2[0] + b1\n",
    "            if (start2[1]-y)*(end2[1]-y)<=0 and (start1[1]-y)*(end1[1]-y)<=0:\n",
    "                return [start2[0], y]\n",
    "        else:#都不是垂线\n",
    "            if k1 == k2 and b1 == b2 and min(start1[1], end1[1])<=max(start2[1], end2[1]) and min(start2[1], end2[1])<=max(start1[1], end1[1]):\n",
    "                #两直线斜率相同、截距相同，类似两条垂线时的判断\n",
    "                return [max(min(start1[0], end1[0]), min(start2[0], end2[0])), max(min(start1[1], end1[1]), min(start2[1], end2[1]))]\n",
    "            elif k1 != k2:#两直线斜率不同\n",
    "                x = (b2-b1)/(k1-k2)\n",
    "                y = k1*x+b1\n",
    "                if (start2[1]-y)*(end2[1]-y)<=0 and (start1[1]-y)*(end1[1]-y)<=0:\n",
    "                    return [x, y]\n",
    "        return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        # 判断 (xk, yk) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "        # 这里的前提是 (xk, yk) 一定在「直线」(x1, y1)~(x2, y2) 上\n",
    "        def inside(x1, y1, x2, y2, xk, yk):\n",
    "            # 若与 x 轴平行，只需要判断 x 的部分\n",
    "            # 若与 y 轴平行，只需要判断 y 的部分\n",
    "            # 若为普通线段，则都要判断\n",
    "            return (x1 == x2 or min(x1, x2) <= xk <= max(x1, x2)) and (y1 == y2 or min(y1, y2) <= yk <= max(y1, y2))\n",
    "        \n",
    "        def update(ans, xk, yk):\n",
    "            # 将一个交点与当前 ans 中的结果进行比较\n",
    "            # 若更优则替换\n",
    "            return [xk, yk] if not ans or [xk, yk] < ans else ans\n",
    "        \n",
    "        x1, y1 = start1\n",
    "        x2, y2 = end1\n",
    "        x3, y3 = start2\n",
    "        x4, y4 = end2\n",
    "\n",
    "        ans = list()\n",
    "        # 判断 (x1, y1)~(x2, y2) 和 (x3, y3)~(x4, y3) 是否平行\n",
    "        if (y4 - y3) * (x2 - x1) == (y2 - y1) * (x4 - x3):\n",
    "            # 若平行，则判断 (x3, y3) 是否在「直线」(x1, y1)~(x2, y2) 上\n",
    "            if (y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1):\n",
    "                # 判断 (x3, y3) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "                if inside(x1, y1, x2, y2, x3, y3):\n",
    "                    ans = update(ans, x3, y3)\n",
    "                # 判断 (x4, y4) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "                if inside(x1, y1, x2, y2, x4, y4):\n",
    "                    ans = update(ans, x4, y4)\n",
    "                # 判断 (x1, y1) 是否在「线段」(x3, y3)~(x4, y4) 上\n",
    "                if inside(x3, y3, x4, y4, x1, y1):\n",
    "                    ans = update(ans, x1, y1)\n",
    "                # 判断 (x2, y2) 是否在「线段」(x3, y3)~(x4, y4) 上\n",
    "                if inside(x3, y3, x4, y4, x2, y2):\n",
    "                    ans = update(ans, x2, y2)\n",
    "            # 在平行时，其余的所有情况都不会有交点\n",
    "        else:\n",
    "            # 联立方程得到 t1 和 t2 的值\n",
    "            t1 = (x3 * (y4 - y3) + y1 * (x4 - x3) - y3 * (x4 - x3) - x1 * (y4 - y3)) / ((x2 - x1) * (y4 - y3) - (x4 - x3) * (y2 - y1))\n",
    "            t2 = (x1 * (y2 - y1) + y3 * (x2 - x1) - y1 * (x2 - x1) - x3 * (y2 - y1)) / ((x4 - x3) * (y2 - y1) - (x2 - x1) * (y4 - y3))\n",
    "            # 判断 t1 和 t2 是否均在 [0, 1] 之间\n",
    "            if 0.0 <= t1 <= 1.0 and 0.0 <= t2 <= 1.0:\n",
    "                ans = [x1 + t1 * (x2 - x1), y1 + t1 * (y2 - y1)]\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        def func(start,end):\n",
    "            x1,y1 = start\n",
    "            x2,y2 = end\n",
    "            if x1==x2:return inf,-inf\n",
    "            k = (y2-y1)/(x2-x1)\n",
    "            b = (x2*y1-x1*y2)/(x2-x1)\n",
    "            return k,b\n",
    "        dots = collections.defaultdict(list)\n",
    "        tmp = [(x1,y1),(x2,y2),(x3,y3),(x4,y4)] = [start1,end1,start2,end2]\n",
    "        xmin,xmax,ymin,ymax = min(x1,x2),max(x1,x2),min(y1,y2),max(y1,y2)\n",
    "        # if not (((xmin<=x3<=xmax or xmin<=x4<=xmax) and (ymin<=y3<=ymax or ymin<=y4<=ymax)) or ((min(x3,x4)<=x1<=max(x3,x4) or min(x3,x4)<=x2<=max(x3,x4)) and (min(y3,y4)<=y1<=max(y3,y4) or min(y3,y4)<=y2<=max(y3,y4)))):\n",
    "        #     print(\"88888\",(xmin<=x3<=xmax or xmin<=x4<=xmax), (ymin<=y3<=ymax or ymin<=y4<=ymax))\n",
    "        #     return []\n",
    "        for x,y in tmp:\n",
    "            dots[x].append(y)\n",
    "        k1,b1 = func(start1,end1)\n",
    "        k2,b2 = func(start2,end2)\n",
    "\n",
    "        if k1==k2:\n",
    "            if b1==b2 and ((xmin<=x3<=xmax or xmin<=x4<=xmax) and (ymin<=y3<=ymax or ymin<=y4<=ymax)):\n",
    "                x = sorted([x1,x2,x3,x4])[1]\n",
    "                y = sorted([y1,y2,y3,y4])[1] if x1==x2==x3==x4 else dots[x][0]\n",
    "                return [round(x,6),round(y,6)]\n",
    "            else:\n",
    "                return []\n",
    "        if k1==inf:\n",
    "            x,y = x1,k2*x1+b2\n",
    "        elif k2==inf:\n",
    "            x,y = x3,k1*x3+b1\n",
    "        else:\n",
    "            x = (b2-b1)/(k1-k2)\n",
    "            y = k1*x+b1\n",
    "\n",
    "        return [round(x,6),round(y,6)] if ymin<=y<=ymax and min(y3,y4)<=y<=max(y3,y4) else []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        # 判断 (xk, yk) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "        # 这里的前提是 (xk, yk) 一定在「直线」(x1, y1)~(x2, y2) 上\n",
    "        def inside(x1, y1, x2, y2, xk, yk):\n",
    "            # 若与 x 轴平行，只需要判断 x 的部分\n",
    "            # 若与 y 轴平行，只需要判断 y 的部分\n",
    "            # 若为普通线段，则都要判断\n",
    "            return (x1 == x2 or min(x1, x2) <= xk <= max(x1, x2)) and (y1 == y2 or min(y1, y2) <= yk <= max(y1, y2))\n",
    "        \n",
    "        def update(ans, xk, yk):\n",
    "            # 将一个交点与当前 ans 中的结果进行比较\n",
    "            # 若更优则替换\n",
    "            return [xk, yk] if not ans or [xk, yk] < ans else ans\n",
    "        \n",
    "        x1, y1 = start1\n",
    "        x2, y2 = end1\n",
    "        x3, y3 = start2\n",
    "        x4, y4 = end2\n",
    "\n",
    "        ans = list()\n",
    "        # 判断 (x1, y1)~(x2, y2) 和 (x3, y3)~(x4, y3) 是否平行\n",
    "        if (y4 - y3) * (x2 - x1) == (y2 - y1) * (x4 - x3):\n",
    "            # 若平行，则判断 (x3, y3) 是否在「直线」(x1, y1)~(x2, y2) 上\n",
    "            if (y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1):\n",
    "                # 判断 (x3, y3) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "                if inside(x1, y1, x2, y2, x3, y3):\n",
    "                    ans = update(ans, x3, y3)\n",
    "                # 判断 (x4, y4) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "                if inside(x1, y1, x2, y2, x4, y4):\n",
    "                    ans = update(ans, x4, y4)\n",
    "                # 判断 (x1, y1) 是否在「线段」(x3, y3)~(x4, y4) 上\n",
    "                if inside(x3, y3, x4, y4, x1, y1):\n",
    "                    ans = update(ans, x1, y1)\n",
    "                # 判断 (x2, y2) 是否在「线段」(x3, y3)~(x4, y4) 上\n",
    "                if inside(x3, y3, x4, y4, x2, y2):\n",
    "                    ans = update(ans, x2, y2)\n",
    "            # 在平行时，其余的所有情况都不会有交点\n",
    "        else:\n",
    "            # 联立方程得到 t1 和 t2 的值\n",
    "            t1 = (x3 * (y4 - y3) + y1 * (x4 - x3) - y3 * (x4 - x3) - x1 * (y4 - y3)) / ((x2 - x1) * (y4 - y3) - (x4 - x3) * (y2 - y1))\n",
    "            t2 = (x1 * (y2 - y1) + y3 * (x2 - x1) - y1 * (x2 - x1) - x3 * (y2 - y1)) / ((x4 - x3) * (y2 - y1) - (x2 - x1) * (y4 - y3))\n",
    "            # 判断 t1 和 t2 是否均在 [0, 1] 之间\n",
    "            if 0.0 <= t1 <= 1.0 and 0.0 <= t2 <= 1.0:\n",
    "                ans = [x1 + t1 * (x2 - x1), y1 + t1 * (y2 - y1)]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        # 计算函数方程，保证不重合\n",
    "        # ax + by = c\n",
    "        # 若c不为0，则保证c=1\n",
    "        def get_abc(x1, y1, x2, y2):\n",
    "            if x1 == x2:\n",
    "                if x1 == 0:\n",
    "                    return 1, 0, 0\n",
    "                return 1 / x1, 0, 1\n",
    "\n",
    "            if y1 == y2:\n",
    "                if y1 == 0:\n",
    "                    return 0, 1, 0\n",
    "                return 0, 1 / y1, 1\n",
    "\n",
    "            # 判断是否过原点\n",
    "            if x1 == 0 and y1 == 0:\n",
    "                return 1, -x2 / y2, 0\n",
    "\n",
    "            if x2 == 0 and y2 == 0:\n",
    "                return 1, -x1 / y1, 0\n",
    "\n",
    "            v = y1 * x2 - y2 * x1\n",
    "            if v == 0:\n",
    "                return 1, -x1 / y1, 0\n",
    "            return (y2 - y1) / -v, (x2 - x1) / v, 1\n",
    "\n",
    "        # 判断是否在中间\n",
    "        def mid(a1, a2, a):\n",
    "            return min(a1, a2) <= a <= max(a1, a2)\n",
    "\n",
    "        x11, y11 = start1\n",
    "        x12, y12 = end1\n",
    "        x21, y21 = start2\n",
    "        x22, y22 = end2\n",
    "\n",
    "        if start1 == end1:\n",
    "            if start2 == end2:\n",
    "                if start1 == start2:\n",
    "                    return start1\n",
    "                return []\n",
    "\n",
    "            if mid(x21, x22, x11) and mid(y21, y22, y11):\n",
    "                a2, b2, c2 = get_abc(x21, y21, x22, y22)\n",
    "                if abs(a2 * x11 + b2 * y11 + c2) <= 0.000001:\n",
    "                    return start1\n",
    "\n",
    "            return []\n",
    "\n",
    "        elif start2 == end2:\n",
    "            if mid(x11, x12, x21) and mid(y11, y12, y21):\n",
    "                a1, b1, c1 = get_abc(x11, y11, x12, y12)\n",
    "                if abs(a1 * x21 + b1 * y21 + c1) <= 0.000001:\n",
    "                    return start2\n",
    "\n",
    "            return []\n",
    "\n",
    "        a1, b1, c1 = get_abc(x11, y11, x12, y12)\n",
    "        a2, b2, c2 = get_abc(x21, y21, x22, y22)\n",
    "\n",
    "        if abs(a2 * x11 + b2 * y11 + c2) <= 0.000001 and abs(a2 * x21 + b2 * y21 + c2) <= 0.000001:\n",
    "            # 两条直线重合\n",
    "            l = [(x11, y11, 1), (x12, y12, 1), (x21, y21, 2), (x22, y22, 2)]\n",
    "            l.sort()\n",
    "\n",
    "            if l[0][-1] != l[1][-1] or l[1][:2] == l[2][:2]:\n",
    "                return l[1][:2]\n",
    "\n",
    "            return []\n",
    "\n",
    "        # 两条线不重合\n",
    "        # 求交点\n",
    "        v = (a2 * b1 - a1 * b2)\n",
    "        if v == 0:\n",
    "            return []\n",
    "        \n",
    "        x = (b2 * c1 - b1 * c2) / -v\n",
    "        y = (a2 * c1 - a1 * c2) / v\n",
    "\n",
    "        if mid(x11, x12, x) and mid(x21, x22, x) and mid(y11, y12, y) and mid(y21, y22, y):\n",
    "            return [x, y]\n",
    "\n",
    "        return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        x1,y1,x2,y2,x3,y3,x4,y4=*start1,*end1,*start2,*end2\n",
    "        det=lambda a,b,c,d:a*d-b*c\n",
    "        d=det(x1-x2,x4-x3,y1-y2,y4-y3)\n",
    "        p=det(x4-x2,x4-x3,y4-y2,y4-y3)\n",
    "        q=det(x1-x2,x4-x2,y1-y2,y4-y2)\n",
    "        if d!=0:\n",
    "            lam,eta=p/d,q/d\n",
    "            if 0<=lam<=1 and 0<=eta<=1:\n",
    "                return [lam*x1+(1-lam)*x2,lam*y1+(1-lam)*y2]\n",
    "            else: return []\n",
    "        if p!=0 or q!=0: return []\n",
    "        t1,t2=sorted([start1,end1]),sorted([start2,end2])\n",
    "        if t1[1]<t2[0] or t2[1]<t1[0]:return []\n",
    "        return max(t1[0],t2[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        def inside(x1, y1, x2, y2, x0, y0):\n",
    "            # 判断(x0, y0)是否在线段上\n",
    "            return (x1 == x2 or min(x1,x2)<=x0<=max(x1,x2)) and (y1 == y2 or min(y1,y2)<=y0<=max(y1,y2))\n",
    "        \n",
    "        def update(res, x0, y0):\n",
    "            # 判断交点与当前结果的大小\n",
    "            return [x0, y0] if not res or [x0, y0] < res else res\n",
    "        \n",
    "        x1,y1 = start1\n",
    "        x2,y2 = end1\n",
    "        x3,y3 = start2\n",
    "        x4,y4 = end2\n",
    "        res = []\n",
    "        if (y4-y3)*(x2-x1) == (y2-y1)*(x4-x3):\n",
    "            if (y2-y1)*(x3-x1) == (y3-y1)*(x2-x1):\n",
    "                if inside(x1, y1, x2, y2, x3, y3):\n",
    "                    res = update(res, x3, y3)\n",
    "                if inside(x1, y1, x2, y2, x4, y4):\n",
    "                    res = update(res, x4, y4)\n",
    "                if inside(x3, y3, x4, y4, x1, y1):\n",
    "                    res = update(res, x1, y1)\n",
    "                if inside(x3, y3, x4, y4, x2, y2):\n",
    "                    res = update(res, x2, y2)\n",
    "            \n",
    "        else:\n",
    "            t1 = (x3*(y4-y3)+y1*(x4-x3)-y3*(x4-x3)-x1*(y4-y3))/((y4-y3)*(x2-x1)-(y2-y1)*(x4-x3))\n",
    "            t2 = (x1*(y2-y1)+y3*(x2-x1)-y1*(x2-x1)-x3*(y2-y1))/((y2-y1)*(x4-x3)-(y4-y3)*(x2-x1))\n",
    "            if 0 <= t1 <= 1 and 0 <= t2 <= 1:\n",
    "                res = [x1+t1*(x2-x1), y1+t1*(y2-y1)]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        def inside(x1, y1, x2, y2, xk, yk):\n",
    "            return (x1 == x2 or min(x1, x2) <= xk <= max(x1, x2)) and (y1 == y2 or min(y1, y2) <= yk <= max(y1, y2))\n",
    "        \n",
    "        def update(ans, xk, yk):\n",
    "            return [xk, yk] if not ans or [xk, yk] < ans else ans\n",
    "\n",
    "        x1, y1 = start1\n",
    "        x2, y2 = end1\n",
    "        x3, y3 = start2\n",
    "        x4, y4 = end2\n",
    "\n",
    "        ans = list()\n",
    "        if (y4 - y3) * (x2 - x1) == (y2 - y1) * (x4 - x3):\n",
    "            if (y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1):\n",
    "                if inside(x1, y1, x2, y2, x3, y3):\n",
    "                    ans = update(ans, x3, y3)\n",
    "                if inside(x1, y1, x2, y2, x4, y4):\n",
    "                    ans = update(ans, x4, y4)\n",
    "                if inside(x3, y3, x4, y4, x1, y1):\n",
    "                    ans = update(ans, x1, y1)\n",
    "                if inside(x3, y3, x4, y4, x2, y2):\n",
    "                    ans = update(ans, x2, y2)\n",
    "        else:\n",
    "            t1 = (x3 * (y4 - y3) + y1 * (x4 - x3) - y3 * (x4 - x3) - x1 * (y4 - y3)) / ((x2 - x1) * (y4 - y3) - (x4 - x3) * (y2 - y1))\n",
    "            t2 = (x1 * (y2 - y1) + y3 * (x2 - x1) - y1 * (x2 - x1) - x3 * (y2 - y1)) / ((x4 - x3) * (y2 - y1) - (x2 - x1) * (y4 - y3))\n",
    "            if 0.0 <= t1 <= 1.0 and 0.0 <= t2 <= 1.0:\n",
    "                ans = [x1 + t1 * (x2 - x1), y1 + t1 * (y2 - y1)]\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        (start1,end1),(start2,end2)=sorted([start1,end1]),sorted([start2,end2]) #保证start在end左边\n",
    "        getAbc=lambda x1,y1,x2,y2: [y2-y1,x1-x2,y1*x2-y2*x1]\n",
    "        a1,b1,c1=getAbc(*start1,*end1)\n",
    "        a2,b2,c2=getAbc(*start2,*end2)        \n",
    "        if a1*b2==a2*b1: #两线平行\n",
    "            if a1*c2==a2*c1 and max(start1,start2)<=min(end1,end2): #重合且有重叠\n",
    "                return sorted([start1,end1,start2,end2])[1]\n",
    "            return [] #不重合或重合但没重叠部分\n",
    "        pt=[(b1*c2-b2*c1)/(a1*b2-a2*b1),(a1*c2-a2*c1)/(b1*a2-b2*a1)]\n",
    "        return pt if start1<=pt<=end1 and start2<=pt<=end2 else []\n",
    "\n",
    "\n",
    "# 数学公式： 已知两点[x1,y1],[x2,y2]求直线ax+by+c=0公式: a=y2-y1, b=x1-x2, c=y1x2-y2x1 已知两直线a1x+b1y+c1=0和a2x+b2y+c2=0求直线交点公式：x=(b1c2-b2c1)/(a1b2-a2b1),y=(a1c2-a2c1)/(b1a2-b2a1) 两直线平行公式：a1b2==a2b1 两直线重叠公式: a1b2==a2b1且a1c2==a2c1 python支持对两个数组求大小，可以利用这个特性判断两个点的左右位置以减少边界条件的判断。\n",
    "\n",
    "# 作者：Justin Yuan\n",
    "# 链接：https://leetcode.cn/problems/intersection-lcci/solutions/334235/python3-jing-jian-10xing-chun-shu-xue-fa-jin-ke-ne/\n",
    "# 来源：力扣（LeetCode）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        k1 = (end1[1] - start1[1]) / (end1[0] - start1[0]) if (end1[0] - start1[0]) else None\n",
    "        b1 = start1[1] - k1 * start1[0] if k1 is not None else None\n",
    "        k2 = (end2[1] - start2[1]) / (end2[0] - start2[0]) if (end2[0] - start2[0]) else None\n",
    "        b2 = start2[1] - k2 * start2[0] if k2 is not None else None\n",
    "\n",
    "        if k1 is None and k2 is None:\n",
    "            if start1[0] == start2[0] and min(start1[1], end1[1])<=max(start2[1], end2[1]) and min(start2[1], end2[1])<=max(start1[1], end1[1]):\n",
    "                return max(min(start1,end1),min(start2,end2))\n",
    "        \n",
    "        elif k1 is None:\n",
    "            y = k2*start1[0] + b2\n",
    "            if (start2[1]-y)*(end2[1]-y)<=0 and (start1[1]-y)*(end1[1]-y)<=0:\n",
    "                return (start1[0],y)\n",
    "        elif k2 is None:\n",
    "            y = k1*start2[0] + b1\n",
    "            if (start2[1]-y)*(end2[1]-y)<=0 and (start1[1]-y)*(end1[1]-y)<=0:\n",
    "                return [start2[0], y]\n",
    "        \n",
    "        else:\n",
    "            if k1 == k2 and b1 == b2 and min(start1[1], end1[1])<=max(start2[1], end2[1]) and min(start2[1], end2[1])<=max(start1[1], end1[1]):\n",
    "                return [max(min(start1[0], end1[0]), min(start2[0], end2[0])), max(min(start1[1], end1[1]), min(start2[1], end2[1]))]\n",
    "            \n",
    "            elif k1 != k2:#两直线斜率不同\n",
    "                x = (b2-b1)/(k1-k2)\n",
    "                y = k1*x+b1\n",
    "                if (start2[1]-y)*(end2[1]-y)<=0 and (start1[1]-y)*(end1[1]-y)<=0:\n",
    "                    return [x, y]\n",
    "        return []\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        k1 = (end1[1]-start1[1])/(end1[0]-start1[0]) if (end1[0]-start1[0]) else None\n",
    "        b1 = start1[1] - k1*start1[0] if k1 is not None else None\n",
    "        k2 = (end2[1]-start2[1])/(end2[0]-start2[0])if (end2[0]-start2[0]) else None\n",
    "        b2 = start2[1] - k2*start2[0] if k2 is not None else None\n",
    "        \n",
    "        if k1 is None and k2 is None: #两条都是垂线\n",
    "            if start1[0] == start2[0] and min(start1[1], end1[1])<=max(start2[1], end2[1]) and min(start2[1], end2[1])<=max(start1[1], end1[1]):\n",
    "                #仅当X相同、直线1的底端小于直线2的顶端、直线2的底端小于直线1的顶端时，才有交点，\n",
    "                #且最小的交点是两直线底端的较大者，如果要最大的交点就是直线顶端的较小者\n",
    "                return max(min(start1, end1), min(start2, end2))\n",
    "        elif k1 is None:#直线1是垂线，直线2不是\n",
    "            y = k2*start1[0] + b2\n",
    "            if (start2[1]-y)*(end2[1]-y)<=0 and (start1[1]-y)*(end1[1]-y)<=0:\n",
    "                return [start1[0], y]\n",
    "        elif k2 is None:#直线2是垂线，直线1不是\n",
    "            y = k1*start2[0] + b1\n",
    "            if (start2[1]-y)*(end2[1]-y)<=0 and (start1[1]-y)*(end1[1]-y)<=0:\n",
    "                return [start2[0], y]\n",
    "        else:#都不是垂线\n",
    "            if k1 == k2 and b1 == b2 and min(start1[1], end1[1])<=max(start2[1], end2[1]) and min(start2[1], end2[1])<=max(start1[1], end1[1]):\n",
    "                #两直线斜率相同、截距相同，类似两条垂线时的判断\n",
    "                return [max(min(start1[0], end1[0]), min(start2[0], end2[0])), max(min(start1[1], end1[1]), min(start2[1], end2[1]))]\n",
    "            elif k1 != k2:#两直线斜率不同\n",
    "                x = (b2-b1)/(k1-k2)\n",
    "                y = k1*x+b1\n",
    "                if (start2[1]-y)*(end2[1]-y)<=0 and (start1[1]-y)*(end1[1]-y)<=0:\n",
    "                    return [x, y]\n",
    "        return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        def func(start,end):\n",
    "            x1,y1 = start\n",
    "            x2,y2 = end\n",
    "            if x1==x2:return inf,-inf\n",
    "            k = (y2-y1)/(x2-x1)\n",
    "            b = (x2*y1-x1*y2)/(x2-x1)\n",
    "            return k,b\n",
    "        dots = collections.defaultdict(list)\n",
    "        tmp = [(x1,y1),(x2,y2),(x3,y3),(x4,y4)] = [start1,end1,start2,end2]\n",
    "        xmin,xmax,ymin,ymax = min(x1,x2),max(x1,x2),min(y1,y2),max(y1,y2)\n",
    "        # if not (((xmin<=x3<=xmax or xmin<=x4<=xmax) and (ymin<=y3<=ymax or ymin<=y4<=ymax)) or ((min(x3,x4)<=x1<=max(x3,x4) or min(x3,x4)<=x2<=max(x3,x4)) and (min(y3,y4)<=y1<=max(y3,y4) or min(y3,y4)<=y2<=max(y3,y4)))):\n",
    "        #     print(\"88888\",(xmin<=x3<=xmax or xmin<=x4<=xmax), (ymin<=y3<=ymax or ymin<=y4<=ymax))\n",
    "        #     return []\n",
    "        for x,y in tmp:\n",
    "            dots[x].append(y)\n",
    "        k1,b1 = func(start1,end1)\n",
    "        k2,b2 = func(start2,end2)\n",
    "\n",
    "        if k1==k2:\n",
    "            if b1==b2 and ((xmin<=x3<=xmax or xmin<=x4<=xmax) and (ymin<=y3<=ymax or ymin<=y4<=ymax)):\n",
    "                x = sorted([x1,x2,x3,x4])[1]\n",
    "                y = sorted([y1,y2,y3,y4])[1] if x1==x2==x3==x4 else dots[x][0]\n",
    "                return [round(x,6),round(y,6)]\n",
    "            else:\n",
    "                return []\n",
    "        if k1==inf:\n",
    "            x,y = x1,k2*x1+b2\n",
    "        elif k2==inf:\n",
    "            x,y = x3,k1*x3+b1\n",
    "        else:\n",
    "            x = (b2-b1)/(k1-k2)\n",
    "            y = k1*x+b1\n",
    "        print(x,y)\n",
    "        return [round(x,6),round(y,6)] if ymin<=y<=ymax and min(y3,y4)<=y<=max(y3,y4) else []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        # 判断 (xk, yk) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "        # 这里的前提是 (xk, yk) 一定在「直线」(x1, y1)~(x2, y2) 上\n",
    "        def inside(x1, y1, x2, y2, xk, yk):\n",
    "            # 若与 x 轴平行，只需要判断 x 的部分\n",
    "            # 若与 y 轴平行，只需要判断 y 的部分\n",
    "            # 若为普通线段，则都要判断\n",
    "            return (x1 == x2 or min(x1, x2) <= xk <= max(x1, x2)) and (y1 == y2 or min(y1, y2) <= yk <= max(y1, y2))\n",
    "        \n",
    "        def update(ans, xk, yk):\n",
    "            # 将一个交点与当前 ans 中的结果进行比较\n",
    "            # 若更优则替换\n",
    "            return [xk, yk] if not ans or [xk, yk] < ans else ans\n",
    "        \n",
    "        x1, y1 = start1\n",
    "        x2, y2 = end1\n",
    "        x3, y3 = start2\n",
    "        x4, y4 = end2\n",
    "\n",
    "        ans = list()\n",
    "        # 判断 (x1, y1)~(x2, y2) 和 (x3, y3)~(x4, y3) 是否平行\n",
    "        if (y4 - y3) * (x2 - x1) == (y2 - y1) * (x4 - x3):\n",
    "            # 若平行，则判断 (x3, y3) 是否在「直线」(x1, y1)~(x2, y2) 上\n",
    "            if (y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1):\n",
    "                # 判断 (x3, y3) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "                if inside(x1, y1, x2, y2, x3, y3):\n",
    "                    ans = update(ans, x3, y3)\n",
    "                # 判断 (x4, y4) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "                if inside(x1, y1, x2, y2, x4, y4):\n",
    "                    ans = update(ans, x4, y4)\n",
    "                # 判断 (x1, y1) 是否在「线段」(x3, y3)~(x4, y4) 上\n",
    "                if inside(x3, y3, x4, y4, x1, y1):\n",
    "                    ans = update(ans, x1, y1)\n",
    "                # 判断 (x2, y2) 是否在「线段」(x3, y3)~(x4, y4) 上\n",
    "                if inside(x3, y3, x4, y4, x2, y2):\n",
    "                    ans = update(ans, x2, y2)\n",
    "            # 在平行时，其余的所有情况都不会有交点\n",
    "        else:\n",
    "            # 联立方程得到 t1 和 t2 的值\n",
    "            t1 = (x3 * (y4 - y3) + y1 * (x4 - x3) - y3 * (x4 - x3) - x1 * (y4 - y3)) / ((x2 - x1) * (y4 - y3) - (x4 - x3) * (y2 - y1))\n",
    "            t2 = (x1 * (y2 - y1) + y3 * (x2 - x1) - y1 * (x2 - x1) - x3 * (y2 - y1)) / ((x4 - x3) * (y2 - y1) - (x2 - x1) * (y4 - y3))\n",
    "            # 判断 t1 和 t2 是否均在 [0, 1] 之间\n",
    "            if 0.0 <= t1 <= 1.0 and 0.0 <= t2 <= 1.0:\n",
    "                ans = [x1 + t1 * (x2 - x1), y1 + t1 * (y2 - y1)]\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        x1,y1,x2,y2,x3,y3,x4,y4=*start1,*end1,*start2,*end2\n",
    "        det=lambda a,b,c,d: a*d-b*c\n",
    "        d=det(x1-x2,x4-x3,y1-y2,y4-y3)\n",
    "        p=det(x4-x2,x4-x3,y4-y2,y4-y3)\n",
    "        q=det(x1-x2,x4-x2,y1-y2,y4-y2)\n",
    "        if d!=0:\n",
    "            lam,eta=p/d,q/d\n",
    "            if not (0<=lam<=1 and 0<=eta<=1):return []\n",
    "            return [lam*x1+(1-lam)*x2,lam*y1+(1-lam)*y2]\n",
    "        if p!=0 or q!=0: return []\n",
    "        t1,t2=sorted([start1,end1]),sorted([start2,end2])\n",
    "        if t1[1]<t2[0] or t2[1]<t1[0]:return []\n",
    "        return max(t1[0],t2[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        # 判断 (xk, yk) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "        # 这里的前提是 (xk, yk) 一定在「直线」(x1, y1)~(x2, y2) 上\n",
    "        def inside(x1, y1, x2, y2, xk, yk):\n",
    "            # 若与 x 轴平行，只需要判断 x 的部分\n",
    "            # 若与 y 轴平行，只需要判断 y 的部分\n",
    "            # 若为普通线段，则都要判断\n",
    "            return (x1 == x2 or min(x1, x2) <= xk <= max(x1, x2)) and (y1 == y2 or min(y1, y2) <= yk <= max(y1, y2))\n",
    "        \n",
    "        def update(ans, xk, yk):\n",
    "            # 将一个交点与当前 ans 中的结果进行比较\n",
    "            # 若更优则替换\n",
    "            return [xk, yk] if not ans or [xk, yk] < ans else ans\n",
    "        \n",
    "        x1, y1 = start1\n",
    "        x2, y2 = end1\n",
    "        x3, y3 = start2\n",
    "        x4, y4 = end2\n",
    "\n",
    "        ans = list()\n",
    "        # 判断 (x1, y1)~(x2, y2) 和 (x3, y3)~(x4, y3) 是否平行\n",
    "        if (y4 - y3) * (x2 - x1) == (y2 - y1) * (x4 - x3):\n",
    "            # 若平行，则判断 (x3, y3) 是否在「直线」(x1, y1)~(x2, y2) 上\n",
    "            if (y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1):\n",
    "                # 判断 (x3, y3) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "                if inside(x1, y1, x2, y2, x3, y3):\n",
    "                    ans = update(ans, x3, y3)\n",
    "                # 判断 (x4, y4) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "                if inside(x1, y1, x2, y2, x4, y4):\n",
    "                    ans = update(ans, x4, y4)\n",
    "                # 判断 (x1, y1) 是否在「线段」(x3, y3)~(x4, y4) 上\n",
    "                if inside(x3, y3, x4, y4, x1, y1):\n",
    "                    ans = update(ans, x1, y1)\n",
    "                # 判断 (x2, y2) 是否在「线段」(x3, y3)~(x4, y4) 上\n",
    "                if inside(x3, y3, x4, y4, x2, y2):\n",
    "                    ans = update(ans, x2, y2)\n",
    "            # 在平行时，其余的所有情况都不会有交点\n",
    "        else:\n",
    "            # 联立方程得到 t1 和 t2 的值\n",
    "            t1 = (x3 * (y4 - y3) + y1 * (x4 - x3) - y3 * (x4 - x3) - x1 * (y4 - y3)) / ((x2 - x1) * (y4 - y3) - (x4 - x3) * (y2 - y1))\n",
    "            t2 = (x1 * (y2 - y1) + y3 * (x2 - x1) - y1 * (x2 - x1) - x3 * (y2 - y1)) / ((x4 - x3) * (y2 - y1) - (x2 - x1) * (y4 - y3))\n",
    "            # 判断 t1 和 t2 是否均在 [0, 1] 之间\n",
    "            if 0.0 <= t1 <= 1.0 and 0.0 <= t2 <= 1.0:\n",
    "                ans = [x1 + t1 * (x2 - x1), y1 + t1 * (y2 - y1)]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        # 判断 (xk, yk) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "        # 这里的前提是 (xk, yk) 一定在「直线」(x1, y1)~(x2, y2) 上\n",
    "        def inside(x1, y1, x2, y2, xk, yk):\n",
    "            # 若与 x 轴平行，只需要判断 x 的部分\n",
    "            # 若与 y 轴平行，只需要判断 y 的部分\n",
    "            # 若为普通线段，则都要判断\n",
    "            return (x1 == x2 or min(x1, x2) <= xk <= max(x1, x2)) and (y1 == y2 or min(y1, y2) <= yk <= max(y1, y2))\n",
    "        \n",
    "        def update(ans, xk, yk):\n",
    "            # 将一个交点与当前 ans 中的结果进行比较\n",
    "            # 若更优则替换\n",
    "            return [xk, yk] if not ans or [xk, yk] < ans else ans\n",
    "        \n",
    "        x1, y1 = start1\n",
    "        x2, y2 = end1\n",
    "        x3, y3 = start2\n",
    "        x4, y4 = end2\n",
    "\n",
    "        ans = list()\n",
    "        # 判断 (x1, y1)~(x2, y2) 和 (x3, y3)~(x4, y3) 是否平行\n",
    "        if (y4 - y3) * (x2 - x1) == (y2 - y1) * (x4 - x3):\n",
    "            # 若平行，则判断 (x3, y3) 是否在「直线」(x1, y1)~(x2, y2) 上\n",
    "            if (y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1):\n",
    "                # 判断 (x3, y3) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "                if inside(x1, y1, x2, y2, x3, y3):\n",
    "                    ans = update(ans, x3, y3)\n",
    "                # 判断 (x4, y4) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "                if inside(x1, y1, x2, y2, x4, y4):\n",
    "                    ans = update(ans, x4, y4)\n",
    "                # 判断 (x1, y1) 是否在「线段」(x3, y3)~(x4, y4) 上\n",
    "                if inside(x3, y3, x4, y4, x1, y1):\n",
    "                    ans = update(ans, x1, y1)\n",
    "                # 判断 (x2, y2) 是否在「线段」(x3, y3)~(x4, y4) 上\n",
    "                if inside(x3, y3, x4, y4, x2, y2):\n",
    "                    ans = update(ans, x2, y2)\n",
    "            # 在平行时，其余的所有情况都不会有交点\n",
    "        else:\n",
    "            # 联立方程得到 t1 和 t2 的值\n",
    "            t1 = (x3 * (y4 - y3) + y1 * (x4 - x3) - y3 * (x4 - x3) - x1 * (y4 - y3)) / ((x2 - x1) * (y4 - y3) - (x4 - x3) * (y2 - y1))\n",
    "            t2 = (x1 * (y2 - y1) + y3 * (x2 - x1) - y1 * (x2 - x1) - x3 * (y2 - y1)) / ((x4 - x3) * (y2 - y1) - (x2 - x1) * (y4 - y3))\n",
    "            # 判断 t1 和 t2 是否均在 [0, 1] 之间\n",
    "            if 0.0 <= t1 <= 1.0 and 0.0 <= t2 <= 1.0:\n",
    "                ans = [x1 + t1 * (x2 - x1), y1 + t1 * (y2 - y1)]\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        def inside(x1,y1,x2,y2,xk,yk):\n",
    "            return (x1 == x2 or min(x1,x2) <= xk <= max(x1,x2)) and (y1 == y2 or min(y1,y2) <= yk <= max(y1,y2))\n",
    "        def update(ans, xk, yk):\n",
    "            return [xk,yk] if not ans or [xk,yk] < ans else ans\n",
    "        x1,y1 = start1\n",
    "        x2,y2 = end1\n",
    "        x3,y3 = start2\n",
    "        x4,y4 = end2\n",
    "\n",
    "        ans = list()\n",
    "\n",
    "        if (y4-y3)*(x2-x1) == (y2-y1)*(x4-x3):\n",
    "            if (y2 - y1) * (x3-x1) == (y3-y1)*(x2-x1):\n",
    "                if inside(x1,y1,x2,y2,x3,y3):\n",
    "                    ans = update(ans, x3,y3)\n",
    "                if inside(x1,y1,x2,y2,x4,y4):\n",
    "                    ans = update(ans, x4,y4)\n",
    "                if inside(x3,y3,x4,y4,x1,y1):\n",
    "                    ans = update(ans,x1,y1)\n",
    "                if inside(x3,y3,x4,y4,x2,y2):\n",
    "                    ans = update(ans,x2,y2)\n",
    "        else:\n",
    "            a = x2-x1\n",
    "            b = x3-x4\n",
    "            c = x3-x1\n",
    "            d = y2-y1\n",
    "            e = y3-y4\n",
    "            f = y3-y1\n",
    "            dom = a*e - b*d\n",
    "            t1 = (c*e-b*f)/dom\n",
    "            t2 = (a*f-d*c)/dom\n",
    "            if 0.0 <= t1 <= 1.0 and 0.0 <= t2 <= 1.0:\n",
    "                ans = [x1 + t1 * (x2-x1), y1+t1*(y2-y1)]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        def func(start,end):\n",
    "            x1,y1 = start\n",
    "            x2,y2 = end\n",
    "            if x1==x2:return inf,-inf\n",
    "            k = (y2-y1)/(x2-x1)\n",
    "            b = (x2*y1-x1*y2)/(x2-x1)\n",
    "            return k,b\n",
    "        dots = collections.defaultdict(list)\n",
    "        tmp = [(x1,y1),(x2,y2),(x3,y3),(x4,y4)] = [start1,end1,start2,end2]\n",
    "        xmin,xmax,ymin,ymax = min(x1,x2),max(x1,x2),min(y1,y2),max(y1,y2)\n",
    "        for x,y in tmp:\n",
    "            dots[x].append(y)\n",
    "        k1,b1 = func(start1,end1)\n",
    "        k2,b2 = func(start2,end2)\n",
    "\n",
    "        if k1==k2:\n",
    "            if b1==b2 and ((xmin<=x3<=xmax or xmin<=x4<=xmax) and (ymin<=y3<=ymax or ymin<=y4<=ymax)):\n",
    "                x = sorted([x1,x2,x3,x4])[1]\n",
    "                y = sorted([y1,y2,y3,y4])[1] if x1==x2==x3==x4 else dots[x][0]\n",
    "                return [round(x,6),round(y,6)]\n",
    "            else:\n",
    "                return []\n",
    "        if k1==inf:\n",
    "            x,y = x1,k2*x1+b2\n",
    "        elif k2==inf:\n",
    "            x,y = x3,k1*x3+b1\n",
    "        else:\n",
    "            x = (b2-b1)/(k1-k2)\n",
    "            y = k1*x+b1\n",
    "\n",
    "        return [round(x,6),round(y,6)] if ymin<=y<=ymax and min(y3,y4)<=y<=max(y3,y4) else []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "sub   = lambda A, B: [A[0] - B[0], A[1] - B[1]]\n",
    "mul   = lambda k, A: [k * A[0], k * A[1]]\n",
    "cross = lambda A, B: A[0] * B[1] - A[1] * B[0]\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        A, B    = sorted([start1, end1])\n",
    "        C, D    = sorted([start2, end2])\n",
    "        a, b, u = sub(B, A), sub(D, C), sub(B, D)\n",
    "        x, y    = cross(a, b), cross(u, b)\n",
    "        if x == 0:\n",
    "            return max(A, C) if y == 0 and max(A, C) <= min(B, D) else []\n",
    "        E = sub(B, mul(y / x, a))\n",
    "        return E if A <= E <= B and C <= E <= D else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        def inside(x1,y1,x2,y2,xk,yk):\n",
    "            return (x1 == x2 or min(x1,x2) <= xk <= max(x1,x2)) and (y1 == y2 or min(y1, y2) <= yk <= max(y1, y2))\n",
    "\n",
    "        def update(ans, xk, yk):\n",
    "            return [xk,yk] if not ans or [xk,yk]<ans else ans\n",
    "        \n",
    "        x1, y1 = start1\n",
    "        x2, y2 = end1\n",
    "        x3, y3 = start2\n",
    "        x4, y4 = end2\n",
    "\n",
    "        ans = list()\n",
    "        # 判断 (x1, y1)~(x2, y2) 和 (x3, y3)~(x4, y3) 是否平行\n",
    "        if (y4 - y3) * (x2 - x1) == (y2 - y1) * (x4 - x3):\n",
    "            # 若平行，则判断 (x3, y3) 是否在「直线」(x1, y1)~(x2, y2) 上\n",
    "            if (y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1):\n",
    "                # 判断 (x3, y3) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "                if inside(x1, y1, x2, y2, x3, y3):\n",
    "                    ans = update(ans, x3, y3)\n",
    "                # 判断 (x4, y4) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "                if inside(x1, y1, x2, y2, x4, y4):\n",
    "                    ans = update(ans, x4, y4)\n",
    "                # 判断 (x1, y1) 是否在「线段」(x3, y3)~(x4, y4) 上\n",
    "                if inside(x3, y3, x4, y4, x1, y1):\n",
    "                    ans = update(ans, x1, y1)\n",
    "                # 判断 (x2, y2) 是否在「线段」(x3, y3)~(x4, y4) 上\n",
    "                if inside(x3, y3, x4, y4, x2, y2):\n",
    "                    ans = update(ans, x2, y2)\n",
    "        else:\n",
    "            # 联立方程得到 t1 和 t2 的值\n",
    "            t1 = (x3 * (y4 - y3) + y1 * (x4 - x3) - y3 * (x4 - x3) - x1 * (y4 - y3)) / ((x2 - x1) * (y4 - y3) - (x4 - x3) * (y2 - y1))\n",
    "            t2 = (x1 * (y2 - y1) + y3 * (x2 - x1) - y1 * (x2 - x1) - x3 * (y2 - y1)) / ((x4 - x3) * (y2 - y1) - (x2 - x1) * (y4 - y3))\n",
    "            # 判断 t1 和 t2 是否均在 [0, 1] 之间\n",
    "            if 0.0 <= t1 <= 1.0 and 0.0 <= t2 <= 1.0:\n",
    "                ans = [x1 + t1 * (x2 - x1), y1 + t1 * (y2 - y1)]\n",
    "\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        line_A_x1, line_A_y1 = start1\n",
    "        line_A_x2, line_A_y2 = end1\n",
    "\n",
    "        line_B_x1, line_B_y1 = start2\n",
    "        line_B_x2, line_B_y2 = end2\n",
    "        \n",
    "        # 计算斜率\n",
    "        if line_A_x1 == line_A_x2:\n",
    "            K_line_A = None\n",
    "        else:\n",
    "            K_line_A = (line_A_y2 - line_A_y1) / (line_A_x2 - line_A_x1)\n",
    "        if line_B_x1 == line_B_x2:\n",
    "            K_line_B = None\n",
    "        else:\n",
    "            K_line_B = (line_B_y2 - line_B_y1) / (line_B_x2 - line_B_x1)\n",
    "        def solve(k, x0, y0, x):\n",
    "            y = y0 + k * (x - x0) + y0\n",
    "            return y\n",
    "        \n",
    "        # 两直线存在垂直的情况\n",
    "        if K_line_A is None or K_line_B is None:\n",
    "            # 两直线都垂直\n",
    "            if K_line_A is None and K_line_B is None:\n",
    "                ay1, ay2 = min(line_A_y1, line_A_y2), max(line_A_y1, line_A_y2)\n",
    "                by1, by2 = min(line_B_y1, line_B_y2), max(line_B_y1, line_B_y2)\n",
    "                if line_A_x1 == line_B_x1 and max(ay1, by1) <= min(ay2, by2):\n",
    "                    return [line_A_x1, max(line_A_y1, line_B_y1)]\n",
    "                else:\n",
    "                    return []\n",
    "            # 有一直线垂直\n",
    "            if K_line_A is None:\n",
    "                #y - line_B_y1 == k(x - lineb_x1)\n",
    "                if line_B_x1 <= line_A_x1 <= line_B_x2:\n",
    "                    solve_y = solve(K_line_B, line_B_x1, line_B_y1, line_A_x1)\n",
    "                    if max(line_A_y1, line_B_y1) <= solve_y <= min(line_A_y2, line_B_y2):\n",
    "                        return [line_A_x1, solve_y]\n",
    "                    else:\n",
    "                        return []\n",
    "                else:\n",
    "                    return []\n",
    "            # 有一直线垂直\n",
    "            if K_line_B is None:\n",
    "                #y - line_B_y1 == k(x - lineb_x1)\n",
    "                if line_A_x1 <= line_B_x1 <= line_A_x2:\n",
    "                    solve_y = solve(K_line_A, line_A_y1, line_A_y1, line_B_x1)\n",
    "                    if max(line_A_y1, line_B_y1) <= solve_y <= min(line_A_y2, line_B_y2):\n",
    "                        return [line_B_x1, solve_y]\n",
    "                    else:\n",
    "                        return []\n",
    "                else:\n",
    "                    return []\n",
    "        \n",
    "        # 两直线均不垂直\n",
    "        # Y = K1(x-xA0)+yA0\n",
    "        # Y = K2(x-xB0)+yB0\n",
    "        # K1(x-xA0)+yA0 = K2(x-xB0)+yB0\n",
    "        # (K1-K2)x = K2xB0+K1XA0+yB0-yA0\n",
    "        print(\"all not ver\")\n",
    "\n",
    "        #平行\n",
    "        if K_line_A == K_line_B:\n",
    "            if line_A_y1 - K_line_A*line_A_x1 == line_B_y1 - K_line_B * line_B_x1:\n",
    "                ay1, ay2 = min(line_A_y1, line_A_y2), max(line_A_y1, line_A_y2)\n",
    "                by1, by2 = min(line_B_y1, line_B_y2), max(line_B_y1, line_B_y2)\n",
    "                ax1, ax2 = min(line_A_x1, line_A_x2), max(line_A_x1, line_A_x2)\n",
    "                bx1, bx2 = min(line_B_x1, line_B_x2), max(line_B_x1, line_B_x2)                \n",
    "                if max(ax1, bx1) <= min(ax2, bx2) and max(ay1, by1) <= min(ay2, by2):\n",
    "                    return [max(line_A_y1, line_B_y1), max(line_A_y1, line_B_y1)]\n",
    "                else:\n",
    "                    return []\n",
    "            else:\n",
    "                return []\n",
    "        print(\"not px\")\n",
    "        x = (-K_line_B * line_B_x1 + K_line_A * line_A_x1 +line_B_y1 -line_A_y1) / (K_line_A - K_line_B)\n",
    "        y = K_line_A* (x - line_A_x1) + line_A_y1\n",
    "        ax1, ax2 = min(line_A_x1, line_A_x2), max(line_A_x1, line_A_x2)\n",
    "        bx1, bx2 = min(line_B_x1, line_B_x2), max(line_B_x1, line_B_x2)\n",
    "\n",
    "        if max(ax1, bx1) <= x <= min(ax2, bx2):\n",
    "            return [x, y]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        \"\"\"\n",
    "        # specical situation vertical\n",
    "        if end1[0] == start1[0] and end2[0] == start2[0]:\n",
    "            if end1[0] != end2[0]:\n",
    "                return []\n",
    "            else:\n",
    "                mn1, mx1 = min(start1[1], end1[1]), max(start1[1], end1[1])\n",
    "                mn2, mx2 = min(start2[1], end2[1]), max(start2[1], end2[1])\n",
    "\n",
    "                if mn1 > mx2 or mn2 < mx1:\n",
    "                    return []\n",
    "                elif mn1 <= mx2 and mn1 > mn2:\n",
    "                    return [end1[0], mn1]\n",
    "                elif mn2 <= mx1 and mn2 > mn1:\n",
    "                    return [end1[0], mn2]\n",
    "                \n",
    "\n",
    "        a1 = (end1[1]-start1[1]) / (end1[0] - start1[0])\n",
    "        b1 = start1[1] - (end1[1]-start1[1]) / (end1[0]-start1[0]) \n",
    "\n",
    "        a2 = (end2[1]-start2[1]) / (end2[0] - start2[0])\n",
    "        b2 = start2[1] - (end2[1]-start2[1]) / (end2[0]-start2[0])\n",
    "\n",
    "        if a1 == a2 and b1 == b2:\n",
    "\n",
    "            x = [start1[0], end1[0], start2[0], end2[0]]\n",
    "            y = [start1[1], end1[1], start2[1], end2[1]]\n",
    "\n",
    "            if a1 > 0 or a1 < 0:\n",
    "                mn = min(x)\n",
    "                idx = x.index(mn)\n",
    "                return [mn, y[idx]]\n",
    "            else:\n",
    "                mx = max(y)\n",
    "                idx = y.index(mx)\n",
    "                return [x[idx], mx]\n",
    "\n",
    "        else:\n",
    "            cross_dotx = (b2-b1)/(a1-a2)\n",
    "\n",
    "            if cross_dotx>=start1[0] and cross_dotx<=end1[0]:\n",
    "                cross_doty = a1 * cross_dotx + b1\n",
    "                return [cross_dotx, cross_doty]\n",
    "            else:\n",
    "                return []\n",
    "        \"\"\"\n",
    "\n",
    "\n",
    "        def inside(x1, y1, x2, y2, xk, yk):\n",
    "            return (x1 == x2 or min(x1, x2) <= xk <= max(x1, x2)) and (y1 == y2 or min(y1, y2) <= yk <= max(y1, y2))\n",
    "        \n",
    "        def update(ans, xk, yk):\n",
    "            return [xk, yk] if not ans or [xk, yk] < ans else ans\n",
    "\n",
    "        x1, y1 = start1\n",
    "        x2, y2 = end1\n",
    "        x3, y3 = start2\n",
    "        x4, y4 = end2\n",
    "\n",
    "        ans = list()\n",
    "        if (y4 - y3) * (x2 - x1) == (y2 - y1) * (x4 - x3):\n",
    "            if (y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1):\n",
    "                if inside(x1, y1, x2, y2, x3, y3):\n",
    "                    ans = update(ans, x3, y3)\n",
    "                if inside(x1, y1, x2, y2, x4, y4):\n",
    "                    ans = update(ans, x4, y4)\n",
    "                if inside(x3, y3, x4, y4, x1, y1):\n",
    "                    ans = update(ans, x1, y1)\n",
    "                if inside(x3, y3, x4, y4, x2, y2):\n",
    "                    ans = update(ans, x2, y2)\n",
    "        else:\n",
    "            t1 = (x3 * (y4 - y3) + y1 * (x4 - x3) - y3 * (x4 - x3) - x1 * (y4 - y3)) / ((x2 - x1) * (y4 - y3) - (x4 - x3) * (y2 - y1))\n",
    "            t2 = (x1 * (y2 - y1) + y3 * (x2 - x1) - y1 * (x2 - x1) - x3 * (y2 - y1)) / ((x4 - x3) * (y2 - y1) - (x2 - x1) * (y4 - y3))\n",
    "            if 0.0 <= t1 <= 1.0 and 0.0 <= t2 <= 1.0:\n",
    "                ans = [x1 + t1 * (x2 - x1), y1 + t1 * (y2 - y1)]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:\n",
    "        # 判断 (xk, yk) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "        # 这里的前提是 (xk, yk) 一定在「直线」(x1, y1)~(x2, y2) 上\n",
    "        def inside(x1, y1, x2, y2, xk, yk):\n",
    "            # 若与 x 轴平行，只需要判断 x 的部分\n",
    "            # 若与 y 轴平行，只需要判断 y 的部分\n",
    "            # 若为普通线段，则都要判断\n",
    "            return (x1 == x2 or min(x1, x2) <= xk <= max(x1, x2)) and (y1 == y2 or min(y1, y2) <= yk <= max(y1, y2))\n",
    "        \n",
    "        def update(ans, xk, yk):\n",
    "            # 将一个交点与当前 ans 中的结果进行比较\n",
    "            # 若更优则替换\n",
    "            return [xk, yk] if not ans or [xk, yk] < ans else ans\n",
    "        \n",
    "        x1, y1 = start1\n",
    "        x2, y2 = end1\n",
    "        x3, y3 = start2\n",
    "        x4, y4 = end2\n",
    "\n",
    "        ans = list()\n",
    "        # 判断 (x1, y1)~(x2, y2) 和 (x3, y3)~(x4, y3) 是否平行\n",
    "        if (y4 - y3) * (x2 - x1) == (y2 - y1) * (x4 - x3):\n",
    "            # 若平行，则判断 (x3, y3) 是否在「直线」(x1, y1)~(x2, y2) 上\n",
    "            if (y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1):\n",
    "                # 判断 (x3, y3) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "                if inside(x1, y1, x2, y2, x3, y3):\n",
    "                    ans = update(ans, x3, y3)\n",
    "                # 判断 (x4, y4) 是否在「线段」(x1, y1)~(x2, y2) 上\n",
    "                if inside(x1, y1, x2, y2, x4, y4):\n",
    "                    ans = update(ans, x4, y4)\n",
    "                # 判断 (x1, y1) 是否在「线段」(x3, y3)~(x4, y4) 上\n",
    "                if inside(x3, y3, x4, y4, x1, y1):\n",
    "                    ans = update(ans, x1, y1)\n",
    "                # 判断 (x2, y2) 是否在「线段」(x3, y3)~(x4, y4) 上\n",
    "                if inside(x3, y3, x4, y4, x2, y2):\n",
    "                    ans = update(ans, x2, y2)\n",
    "            # 在平行时，其余的所有情况都不会有交点\n",
    "        else:\n",
    "            # 联立方程得到 t1 和 t2 的值\n",
    "            t1 = (x3 * (y4 - y3) + y1 * (x4 - x3) - y3 * (x4 - x3) - x1 * (y4 - y3)) / ((x2 - x1) * (y4 - y3) - (x4 - x3) * (y2 - y1))\n",
    "            t2 = (x1 * (y2 - y1) + y3 * (x2 - x1) - y1 * (x2 - x1) - x3 * (y2 - y1)) / ((x4 - x3) * (y2 - y1) - (x2 - x1) * (y4 - y3))\n",
    "            # 判断 t1 和 t2 是否均在 [0, 1] 之间\n",
    "            if 0.0 <= t1 <= 1.0 and 0.0 <= t2 <= 1.0:\n",
    "                ans = [x1 + t1 * (x2 - x1), y1 + t1 * (y2 - y1)]\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef intersection(self, start1, end1, start2, end2):\n",
    "\t\tif start1[0] > end1[0]:\n",
    "\t\t\tstart1, end1 = end1, start1\n",
    "\t\tif start2[0] > end2[0]:\n",
    "\t\t\tstart2, end2 = end2, start2\n",
    "\t\tif max(start1[0], start2[0]) > min(end1[0], end2[0]):\n",
    "\t\t\treturn []\n",
    "\t\tif start1 == end1 == start2 == end2: #4点重合\n",
    "\t\t\treturn start1\n",
    "\t\tif start1 == end1: #2点重合在另一线段上\n",
    "\t\t\treturn start1 if (start1[0] - start2[0]) * (start2[1] - end2[1]) == (start1[1] - start2[1]) * (start2[0] - end2[0]) else []\n",
    "\t\tif start2 == end2:\n",
    "\t\t\treturn start2 if (start2[0] - start1[0]) * (start1[1] - end1[1]) == (start2[1] - start1[1]) * (start1[0] - end1[0]) else []\n",
    "\t\ta1, b1, c1 = self.calc(start1, end1)\n",
    "\t\ta2, b2, c2 = self.calc(start2, end2)\n",
    "\t\tif a1 * b2 == a2 * b1: #直线平行\n",
    "\t\t\tif a1 * c2 == a2 * c1: #直线重合\n",
    "\t\t\t\tx, y = max(start1, start2)\n",
    "\t\t\telse:\n",
    "\t\t\t\treturn []\n",
    "\t\telse:\n",
    "\t\t\tx = (c1 * b2 - c2 * b1) / (a2 * b1 - a1 * b2)\n",
    "\t\t\ty = -(c1 + a1 * x) / b1 if b1 != 0 else -(c2 + a2 * x) / b2\n",
    "\t\treturn [x, y] if self.chk(start1, end1, x, y) and self.chk(start2, end2, x, y) else []\n",
    "\t\n",
    "\tdef calc(self, p1, p2):\n",
    "\t\tif p1[0] == p2[0]:\n",
    "\t\t\treturn [1, 0, -p1[0]]\n",
    "\t\tif p1[1] == p2[1]:\n",
    "\t\t\treturn [0, 1, -p1[1]]\n",
    "\t\tdx = p2[0] - p1[0]\n",
    "\t\tdy = p2[1] - p1[1]\n",
    "\t\treturn [dy, -dx, dx * p1[1] - dy * p1[0]]\n",
    "\t\n",
    "\tdef chk(self, p1, p2, x, y):\n",
    "\t\treturn min(p1[0], p2[0]) <= x <= max(p1[0], p2[0]) and min(p1[1], p2[1]) <= y <= max(p1[1], p2[1])"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
